//
// Created by cheng on 2021/02/23.
// 02-23 未解决
//

#include <iostream>
#include <vector>

using namespace std;

int Count(vector<int> v, int left, int mid, int right);
// 求逆序数
int GetInversions(const vector<int>& v, int left, int right);

int main () {

}

int GetInversions(const vector<int>& v, int left, int right) {
    if (left < right - 1) {
        int mid = (right + left) / 2;
        auto num1 = GetInversions(v, left, mid);
        auto num2 = GetInversions(v, mid, right);
        auto num3 = Count(v, left, mid, right);
        return num1+num2+num3;
    }
    return 0;
}

int Count(vector<int> v, int left, int mid, int right) {
    int len1 = mid-left, len2 = right-mid;
    int res = 0;

    auto arr1 = new int[len1];
    auto arr2 = new int[len2];

    for (int i = 0; i < len1; i++) {
        arr1[i] = v[left + i];
    }
    for (int i = 0; i < len2; i++) {
        arr2[i] = v[mid + i];
    }
    for (int k = left, i = 0, j = 0; k < right; k++) {
        if (arr1[i] <= arr2[j]) {
            v[k] = arr1[i++];
        } else {
            v[k] = arr2[j++];
        }

    }
    delete[] arr1;
    delete[] arr2;
    return res;
}
